package com.leecode;

import java.util.PriorityQueue;

/**
 * 数组中的第K个最大元素
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 几ms的算法是怎么写出来的???!!!
 */
public class Leet215 {
	public static void main(String[] args) {
		int[] ints = {3, 2, 1, 5, 6, 4};
		System.out.println(new Leet215().findKthLargest(ints, 2));
//		ints = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
//		System.out.println(findKthLargest(ints, 4));
	}

	/**
	 * bubble写个串串,58ms???????????????直接O(n*k),
	 * 90%,87%,2ms Arrays.sort,O(nlogn)
	 * 99%,1ms
	 */
	public static int findKthLargest2(int[] nums, int k) {
		for (int i = 1; i <= k; i++) {
			for (int j = nums.length - i;j >= 0;  j--) {
				if (nums[j] >nums[nums.length-i]) {
					int temp= nums[j];
					nums[j]=nums[nums.length-i];
					nums[nums.length-i]=temp;
				}
			}
		}
		return nums[nums.length - k];
	}

	/**
	 *
	 */
	public int findKthLargest(int[] nums, int k) {
		int len = nums.length;
		// 使用一个含有 len 个元素的最小堆，默认是最小堆，可以不写 lambda 表达式：(a, b) -> a - b
		PriorityQueue<Integer> minHeap = new PriorityQueue<>(len, (a, b) -> a - b);
		for (int i = 0; i < len; i++) {
			minHeap.add(nums[i]);
		}
		for (int i = 0; i < len - k; i++) {
			minHeap.poll();
		}
		return minHeap.peek();
	}




}
